Linear transformations are commonly used for signal or data processing. A linear transformation produce from an n-dimensional vector, considered as “input vector” an r-dimensional vector, considered as “output vector”. In many applications the input vector consists of digital samples of a given signal that requires processing. However applications of linear transformations are not restricted to any specific domain, they are essential to every field of science and technology and their efficient performance is highly desirable.
A general linear transformation from the set of n-dimensional vectors (real, complex or from any field of scalars) to the set of r-dimensional vectors (over the same field of scalars), may be represented by a matrix of order rxn given by:   A  =      [                   ⁢                                        a            11                                                a            12                                    …                                      a                          1              ⁢              n                                                                        a            21                                                a            22                                    …                                      a                          2              ⁢              n                                                            ⋮                                                                                                                                                                                                     a            r1                                                                                                                                                  a            rn                                ⁢                   ]  
A general input n-dimensional column vector is written in the following form:   x  =      [                   ⁢                                        x            1                                                            x            2                                                ⋮                                                  x            n                                ⁢                   ]  
The linear transformation produce from the input vector x an output column vector, y of dimension r, through the product of the matrix by the vector which is given by following formula:   y  =            [                           ⁢                                                  y              1                                                                          y              2                                                            ⋮                                                              y              r                                          ⁢                           ]        =                            [                                           ⁢                                                                      a                  11                                                                              a                  12                                                            …                                                              a                                      1                    ⁢                    n                                                                                                                        a                  21                                                                              a                  22                                                            …                                                              a                                      2                    ⁢                    n                                                                                                      ⋮                                                                                                                                                                                                                                                                                                                                   a                  r1                                                                                                                                                                                                                                            a                  rn                                                              ⁢                                           ]                [                                   ⁢                                                            x                1                                                                                        x                2                                                                        ⋮                                                                          x                n                                                    ⁢                                   ]            =              [                                   ⁢                                                                                                  a                    11                                    ⁢                                      x                    1                                                  +                                                                                                          a                    12                                    ⁢                                      x                    2                                                  +                                                    …                                                                        +                                      a                                          1                      ⁢                      n                                                                      ⁢                                  x                  n                                                                                                                                              a                    21                                    ⁢                                      x                    1                                                  +                                                                                                          a                    22                                    ⁢                                      x                    2                                                  +                                                    …                                                                        +                                      a                                          2                      ⁢                      n                                                                      ⁢                                  x                  n                                                                                        ⋮                                      ⋮                                                                                                           ⋮                                                                                            a                  r1                                ⁢                                  x                  1                                                                                                                          a                    r2                                    ⁢                                      x                    2                                                  +                                                    …                                                                        +                                      a                    rn                                                  ⁢                                  x                  n                                                                    ⁢                                   ]            
A straightforward performance of the linear transformation requires, r·n products and r·(n−1) additions.
Binary matrix are of special importance in the development and application of the present invention. Binary-bipolar matrix are those containing only ±1 values in their entries. Henceforth they would be called U-matrix. A linear transformation represented by a U-matrix will be called U-transformation. In the above presentation, if the given transformation is a U-transformation then r·(n−1) additions/subtractions would be required for its straightforward performance. Another type of binary matrix are those containing only 0,1 values in their entries. They would be called 0-1-matrix. A linear transformation represented by 0-1-matrix is called a 0-1-transformation. In the above presentation, r·(n−1)/2 additions would be required, on average, for a straightforward performance of a 0-1-transformation.
In the current text the term “binary transformation” would consist of the two types of transformations mentioned above: U-transformations and 0-1-transformations. To complete the terminology-introduction it would be mentioned that the term U-vector would refer to a vector having ±1 values in its components and likewise, a vector having 0,1 values in its components will be called a 0-1-vector.
The processing of binary transformations consist of adding and subtracting components of the input vector. They are implemented in hardware as an electronic Application Specific Integrated Circuit (ASIC), requiring elements such as adders and subtractors. The usage of these components is costly and energy consuming and their construction occupies a precious area. A hardware implementation of binary transformations with a low consumption of these resources is of increasing need in numerous fields of technology.
There is a widespread usage of U-transformations in various aspects of digital signal processing. It includes a variety of communication technologies such as image processing and wireless communication.
Currently there is a growing worldwide interest in direct-sequence (DS) code division multiple access (CDMA) spread spectrum communication systems. The IS-95 [TIA/EIA/IS-95-A, “Mobile Station Base Station Compatibility Standard for Dual-Mode Wideband Spread spectrum Cellular System”, Feb. 27, 1996] is one example of the developing DS-CDMA systems.
In the CDMA transmission technique a multi-user data is send in a composite signal and then multiplied before transmission by a Pseudo-random Noise (PN) code, which is a U-sequence having random noise properties (such as low cross-correlation). The spreading properties makes transmission resistance to noise, including multi-path noise, jamming or detection. A scrambling code, longer than the channeling code, is also applied. This transmission fashion of the second generation (IS-95-B) and third generation (3G) wide band (WB) CDMA standards require the receiver to perform multi-code detection. This is a task of despreading the combined channels simultaneously, each of which was previously spread according to a different channeling code. It is done by application of U-transformations where the spreading codes comprising the transformation matrix are often rows of a Hadamard matrix. This is one of the many examples where effective U-transformation techniques are desired for accomplishing the computational tasks with a low consumption of resources.
There are several known mechanisms that improve the performance of specific types of linear transformations. A few relevant examples chosen from a very wide range will be mentioned here. Toplitz transformations which perform convolutions and are used as filters in DSP can be done efficiently by the use of the classical Fast Fourier Transform (FFT) algorithm requiring O(n·log2(n)) addition and multiplication operations, where n is the dimension of the domain space. In comparison the standard, straightforward methods, require O(n2) addition and multiplication. For details see: [James W. Cooley and John W. Tukey, “An algorithm for the machine calculation of complex Fourier series”, Mathematics of computation, 19 (90): 297-301, April 1965.]
A specific type of U-transformation used in digital signal processing including CDMA technologies is the Walsh-Hadamard Transformation which is represented by a Hadamard matrix. A Hadamard matrix can be defined recursively as follows:             H      1        =          [      1      ]        ,           ⁢            H      2        =          [                           ⁢                                    1                                1                                                1                                              -              1                                          ⁢                           ]        ,and for every integer n, a power of 2:       H          2      ⁢      n        =      [                   ⁢                                        H            n                                                H            n                                                            H            n                                                -                          H              n                                            ⁢                   ]  
A low complexity and energy preserving algorithm for performing this transformation is the Fast Walsh-Hadamard Transform (FWT), which reduces the number of additions/subtractions for nxn Hadamard matrix to n·log2(n). This provides an optimal saving in these operations. The fundamental ideas underlining this method are similar to those of the FFT
The U-transformation's aspect is modified by another feature of the invention to accommodate for an efficient method and apparatus for the performance of and toplitz U-transformations. These transformations represents full or partial convolution with a given U-sequence or a complex U-sequence. Wireless communication applications of toplitz U-transformations include initial time-synchronization and the searcher which use convolutions with a real or complex pseudo-random (PN) or gold, U-sequences. A gold sequence is composed by the Z2 sum of two PN sequences.
The above binary aspects of the invention are generalized by another aspect of the invention to an efficient method and apparatus for the performance of a linear transformation, represented by an rxn matrix with a relatively small number of different entries. Applications of this advanced aspect of the invention include complex U-transformations and linear transformations represented by an matrix with {0, 1, −1}-entries. This broad preferred embodiment of the invention would be called the generalized-elimination-method (GEM).
Wide band CDMA and probably other branches of advanced DSP future technologies would benefit from the simultaneous analysis of an incoming signal in different spreading factors. This would give way to a multi-code channel that allows the simultaneous reception of different type of information such as fax, normal phone conversation and internet data without overburdening the network. Another aspect of the present invention is an efficient method and apparatus for these type of linear operations. It comprises modified versions of the U-binary aspect of the invention with an additional processor. This additional processor uses information about the number of additions required by the said U-binary method to discover a configuration that applies the U-binary method in various subsections in global low rate of additions.
Additional major applications of the invention include wireless multimedia systems personal satellite mobile systems, GPS satellite-based locating systems and more. In the context of mobile communication and other mobile, computational based, systems a reduction in current consumption used for linear processing is essential. Applications of the invention the in the mobile phone technologies can prolong the life of the battery, reduce circuitry and shorten response time.